Operating System
Page Replacement in OS
Page Replacement
Page replacement is a memory-management technique used by an operating system in a virtual memory system. It determines which page currently in main memory (RAM) should be removed when a new page needs to be loaded but there is no free frame available.
Why is Page Replacement Needed?
A process may require more memory than the available physical RAM. The operating system therefore divides the process into fixed-size pages and RAM into fixed-size frames.
When a required page is not currently in RAM, a page fault occurs.The basic process is:
- CPU requests a page.
- OS checks whether the page is in RAM.
- If the page is present -> Page Hit.
- If the page is absent -> Page Fault.
- If a free frame exists, the required page is loaded into it.
- If no free frame exists, the OS selects a victim page for replacement.
- The victim page is removed and the required page is loaded.
- Execution continues.
Example Suppose RAM has 3 frames, and the following page-reference string is given: 1, 2, 3, 4 Initially:
| Frame | Page |
|---|---|
| F1 | 1 |
| F2 | 2 |
| F3 | 3 |
Now the CPU requests page 4. There is no free frame, so the operating system must remove one of pages 1, 2, or 3 and put page 4 in its place. Which page should be removed?
That depends on the page replacement algorithm being used.Major Page Replacement Algorithms
FIFO - First In, First Out
The page that entered memory first is removed first. For example:
1 -> 2 -> 3
If page 4 must be loaded, page 1 is replaced because it entered memory first.- Advantage: Simple to implement.
- Disadvantage: It may remove a page that is still frequently used.
Optimal Page Replacement
The operating system replaces the page that will not be used for the longest period of time in the future.For example, if the pages currently in memory are:
1, 2, 3
and the future references are:2, 1, 4, 2, 3
Page 3 would be replaced because it is needed farthest in the future.- Advantage: Produces the minimum possible number of page faults.
- Disadvantage: The operating system cannot actually know future memory references, so it is mainly used as a benchmark for comparison.
LRU - Least Recently Used
LRU replaces the page that has not been used for the longest time in the past. For example: If pages have recently been accessed in this order:
2 -> 1 -> 3
then page 2 is the oldest among these three accesses. If a replacement is needed, LRU may select page 2.- Advantage: Usually performs better than FIFO.
- Disadvantage : Tracking page usage requires additional overhead.
Second-Chance / Clock
This is an improvement over FIFO. Each page has a reference bit. A page that has been recently used gets a second chance instead of being immediately replaced. It is commonly implemented using a circular queue (clock).
A system has 3 page frames and the following reference string:
7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2
Find the number of page faults and page hits using:
- FIFO
- LRU
- Optimal Page Replacement
FIFO - First-In, First-Out
In FIFO, the page that entered memory first is replaced first.| Reference | Frame 1 | Frame 2 | Frame 3 | Result |
|---|---|---|---|---|
| 7 | 7 | - | - | Fault |
| 0 | 7 | 0 | - | Fault |
| 1 | 7 | 0 | 1 | Fault |
| 2 | 2 | 0 | 1 | Fault |
| 0 | 2 | 0 | 1 | Hit |
| 3 | 2 | 3 | 1 | Fault |
| 0 | 2 | 3 | 0 | Fault |
| 4 | 4 | 3 | 0 | Fault |
| 2 | 4 | 2 | 0 | Fault |
| 3 | 4 | 2 | 3 | Fault |
| 0 | 0 | 2 | 3 | Fault |
| 3 | 0 | 2 | 3 | Hit |
| 2 | 0 | 2 | 3 | Hit |
- Number of references: 13
- Number of faults: 10
- Number of hits: 13 -10 = 3
- Page-Fault Ratio: 10/13 *100=76.92%
LRU - Least Recently Used
LRU replaces the page that has not been used for the longest period of time.
Reference string:7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2
| Reference | Frame 1 | Frame 2 | Frame 3 | Result |
|---|---|---|---|---|
| 7 | 7 | - | - | Fault |
| 0 | 7 | 0 | - | Fault |
| 1 | 7 | 0 | 1 | Fault |
| 2 | 2 | 0 | 1 | Fault |
| 0 | 2 | 0 | 1 | Hit |
| 3 | 2 | 0 | 3 | Fault |
| 0 | 2 | 0 | 3 | Hit |
| 4 | 4 | 0 | 3 | Fault |
| 2 | 4 | 0 | 2 | Fault |
| 3 | 4 | 0 | 3 | Hit |
| 0 | 4 | 0 | 3 | Hit |
| 3 | 4 | 0 | 3 | Hit |
| 2 | 2 | 0 | 3 | Fault |
- Page Faults: 8
- Page Hits: 13 - 8 = 5
- Page-Fault Ratio: 8/13*100 = 61.54%
Optimal Page Replacement
Optimal replacement removes the page that will be needed farthest in the future.Reference string:
7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2
| Reference | Frame 1 | Frame 2 | Frame 3 | Result |
|---|---|---|---|---|
| 7 | 7 | - | - | Fault |
| 0 | 7 | 0 | - | Fault |
| 1 | 7 | 0 | 1 | Fault |
| 2 | 2 | 0 | 1 | Fault |
| 0 | 2 | 0 | 1 | Hit |
| 3 | 2 | 0 | 3 | Fault |
| 0 | 2 | 0 | 3 | Hit |
| 4 | 2 | 4 | 3 | Fault |
| 2 | 2 | 4 | 3 | Hit |
| 3 | 2 | 4 | 3 | Hit |
| 0 | 0 | 4 | 3 | Fault |
| 3 | 0 | 4 | 3 | Hit |
| 2 | 0 | 2 | 3 | Fault |
- Page Faults: 7
- Page Hits: 13 - 7 = 6
- Page-Fault Ratio: 7/13*100 = 53.85%